package practise;

import java.util.Arrays;
import java.util.NoSuchElementException;

/**
 * @ClassName Heap
 * @Description TODO
 * @Author ZJX
 * @Date 2024/7/29 15:12
 * @Version 1.0
 */

// 删除堆顶元素 构建初始堆  使用向下调整
//    插入新元素 改变节点值  使用向上调整

public class Heap {

    public int[] elems;
    public int usedSize; // 有效元素个数

    private static final int DEFAULT_INITAL_CAPACITY = 11; //底层源码默认初始内部容量
    public Heap() {
        this.elems = new int[DEFAULT_INITAL_CAPACITY];
    }

//    堆的初始化
    public void initElem(int[] arr){
        for (int i = 0; i < elems.length; i++) {
            elems[i] = arr[i];
            usedSize++;
        }
    }

    /*
     * @param :
      * @return void
     * @author: ZJX
     * @description:  创建小根堆 小根堆更常考察
     *  从最后一颗子树开始调整 用根节点与左右孩子节点进行比较
     *  向下调整 heapifyDown算法 的时间复杂度为 O(N)
     * @date: 2024/7/29 15:18
     */
    public void createHeap(){
//        usedSize为有效元素个数, 因为数组从零开始所以usedSize-1.
//        最后一课子树的位置为 (i - 1)/2     i = usedSize - 1;
        for (int parent = ((usedSize-1)-1)/2; parent >= 0; parent--) {
            heapifyDown(parent);
        }
    }

    private void heapifyDown(int parent) {
        int leftChild = 2*parent+1;
        int rightChild = 2*parent+2;
        int smallest = parent; // 记录最小值的索引

//        左孩子存在且值小于当前索引最小值
        if (leftChild < usedSize && elems[leftChild] < elems[smallest]){
            smallest = leftChild;
        }

//        右孩子存在且值小于当前索引最小值
        if (rightChild < usedSize && elems[rightChild] < elems[smallest]){
            smallest = rightChild;
        }

//        此时说明小根堆的根节点已经改变
        if (smallest != parent){
            int temp = elems[parent];
            elems[parent] = elems[smallest];
            elems[smallest] = temp;

            // 递归向下调整
            heapifyDown(smallest);
        }
    }

    /*
     * @param value:
      * @return void
     * @author: ZJX
     * @description:  小根堆 添加元素
     * @date: 2024/7/29 21:02
     */
    public void add(int value) {
//        1. 满了 扩容
        if (isFull()){
            this.elems = Arrays.copyOf(elems,2*elems.length);
        }

        // 2. 将新元素添加到堆的末尾
        elems[usedSize] = value;

        // 3. 向上调整，保持小根堆的性质
        heapifyUp(usedSize);

        // 4. 更新已使用的大小
        usedSize++;
    }

//    判断堆是否已满
    public boolean isFull(){
        return usedSize == elems.length;
    }

    /*
     * @param child:
      * @return void
     * @author: ZJX
     * @description: 向上调整
     *  其实向上调整也可以建堆 但其时间复杂度比向下调整O(N)复杂度高
     *      向上调整的时间复杂度为 O(N*logN)
     * @date: 2024/7/29 21:40
     */
    private void heapifyUp(int child){
        int parent = (child - 1)/2;

//        child > 0 因为 递归到 root 根节点 不能再递归了
        while (child > 0 && elems[child] < elems[parent]){
//            交换 孩子节点跟根节点 的位置
            int temp = elems[parent];
            elems[parent] = elems[child];
            elems[child] = temp;

            child = parent;
            parent = (child - 1)/2;
        }
    }

    /*
     * @param :
      * @return int
     * @author: ZJX
     * @description: 堆的删除 每次删的是堆顶元素
     * @date: 2024/7/29 21:45
     */
    public int poll() {
//        1. 判断是否为空
        if (empty()){
            throw new NoSuchElementException("Heap is empty");
        }

//        记录堆顶元素
        int root = elems[0];

//        用最后一个元素顶替堆顶元素 然后usedSize减一 再调整
        elems[0] = elems[usedSize-1];

        usedSize--; // 此时 堆顶元素再最后 被删除了

        heapifyDown(0); //向下调整

        return root;
    }

    public boolean empty(){
        return usedSize == 0;
    }


}


